package yz.com.javautil.roadNetwork;


import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.Vector;

/**
 * 寻路
 * 参考资料：https://www.runoob.com/data-structures/graph-theory-path.html
 *
 * @author runoob
 */
public class Path {
    /**
     * 图的引用
     */
    private Graph graph;
    /**
     * 起始点
     */
    private int startPoint;
    /**
     * 记录dfs的过程中节点是否被访问
     */
    private boolean[] visited;
    /**
     * 记录路径, from[i]表示查找的路径上i的上一个节点
     */
    private int[] from;

    /**
     * 构造函数
     * 寻路算法(寻找图 graph 从 startPoint 点到其他点的路径)
     *
     * @param graph      图对象
     * @param startPoint 起点
     */
    public Path(Graph graph, int startPoint) {
        // 算法初始化
        this.graph = graph;
        assert startPoint >= 0 && startPoint < this.graph.getNodeNum();
        visited = new boolean[this.graph.getNodeNum()];
        from = new int[this.graph.getNodeNum()];
        for (int i = 0; i < this.graph.getNodeNum(); i++) {
            visited[i] = false;
            from[i] = -1;
        }
        this.startPoint = startPoint;
        // 寻路算法
        dfs(startPoint);
    }

    /**
     * 图的深度优先遍历
     *
     * @param vertex 顶点
     */
    private void dfs(int vertex) {
        visited[vertex] = true;
        for (int point : graph.getAdjacentEdge(vertex)) {
            if (!visited[point]) {
                from[point] = vertex;
                dfs(point);
            }
        }
    }

    /**
     * 查询从s点到w点是否有路径
     *
     * @param w 点
     * @return 是否存在路径
     */
    private boolean hasPath(int w) {
        assert w >= 0 && w < graph.getNodeNum();
        return visited[w];
    }

    /**
     * 查询从s点到w点的路径, 存放在vec中
     *
     * @param w 目标点
     * @return 路径
     */
    private Vector<Integer> path(int w) {
        assert hasPath(w);
        Stack<Integer> s = new Stack<>();
        // 通过from数组逆向查找到从s到w的路径, 存放到栈中
        int p = w;
        while (p != -1) {
            s.push(p);
            p = from[p];
        }
        // 从栈中依次取出元素, 获得顺序的从s到w的路径
        Vector<Integer> res = new Vector<>();
        while (!s.empty()) {
            res.add(s.pop());
        }
        return res;
    }

    /**
     * 打印出从s点到w点的路径（测试用）
     *
     * @param w 目标点
     */
    public void showPath(int w) {
        assert hasPath(w);
        Vector<Integer> vec = path(w);
        for (int i = 0; i < vec.size(); i++) {
            System.out.print(vec.elementAt(i));
            if (i == vec.size() - 1) {
                System.out.println();
            } else {
                System.out.print(" -> ");
            }
        }
    }

    /**
     * 返回从s点到w点的路径
     *
     * @param w 目标点
     * @return 路径
     */
    public Vector<Integer> getPath(int w) {
        assert hasPath(w);
        return path(w);
    }
}
